package com.ahpu.lyf.recursion;

public class Queen8 {
    public static void main(String[] args) {
        Queen queen=new Queen();
        queen.getResult();
    }
}


/**
 * 直接使用一维数组解决，下标代表第几行也就是第几个皇后，对应下标的值表示放在那个位置，
 */
class Queen{
    private final int[] arr=new int[8];
    private int count;

    public void getResult(){
        check(0);
        System.out.println("共有"+count+"种解法!");
    }


    /**
     * 放置皇后位置
     * @param n 放置的皇后，从第0个开始
     */
    private void check(int n){
        //如果n==MAX说明皇后放完了
        int MAX = 8;
        if (n== MAX){
            //打印这次放置的数组
            print();
            //方法执行完毕弹栈，回溯到上次调用
        }else {
            //从第一列开始放
            for (int i = 0; i < MAX; i++) {
                //将第n个皇后放在第i列
                arr[n]=i;
                //判断此皇后是否冲突，不冲突则进入下一个皇后的放置，冲突则将皇后向下一列放
                if (judge(n)){
                    check(n+1);
                }
            }
        }
    }

    /**
     * 判断皇后之间是否冲突
     * @param n 要判断的皇后
     * @return 判断结果
     */
    private Boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //循环与前几个皇后比较
            //第i个皇后的值即为放置的列数，如果和第n个皇后相等则冲突
            //abs(n-i)可以理解为棋盘中两个皇后之间的列数差，abs(arr[n]-arr[i])可以理解为棋盘中两个皇后的行数差，相等说明在一条对角线上（arr[n]表示第n个皇后放置的列数，下标n表示第n个皇后放置的行数）
            if (arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }

    /**
     * 打印结果的方法
     */
    private void print(){
        count++;
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}
